package Heap;

import java.util.*;

class IntCmp implements Comparator<Integer> {
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}

public class TestHeap {

    //    最小k个数
    public static int[] smallestK1(int[] arr, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for(int i=0;i<arr.length;i++) {
            minHeap.offer(arr[i]);
        }
        int[] tmp=new int[k];
        for(int i=0;i<k;i++) {
            int val=minHeap.poll();
            tmp[i]=val;
        }
        return tmp;
    }

    public static int[] smallestK2(int[] arr, int k) {
        int[] tmp=new int[k];
        if(k==0) return tmp;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new IntCmp());
        //1. 把前k个元素放入k中
        for(int i=0;i<k;i++) {
            maxHeap.offer(arr[i]);
        }
        //2. 遍历剩下的n-k个元素
        for(int i=k;i<arr.length;i++) {
            int val=maxHeap.peek();
            if(val>arr[i]) {
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
        }
        for(int i=0;i<k;i++) {
            tmp[i]=maxHeap.poll();
        }
        return tmp;
    }

    public static void main4(String[] args) {
        int[] array={27,15,19,18};
        int[] ret=smallestK2(array,3);
        System.out.println(Arrays.toString(ret));
    }


    public static void main(String[] args) {

        //优先队列实现了collection接口，可以接收list作为参数
        List<Integer> list=new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);

        //优先队列默认是小根堆
        PriorityQueue<Integer> pq=new PriorityQueue<>(new IntCmp());
        pq.offer(12);
        pq.offer(13);
        pq.offer(14);
        System.out.println(pq.peek());
    }



    public static void main1(String[] args) {
        Heap heap=new Heap();
        int[] array={27,15,19,18,28,34,65,49,25,37};
        heap.init(array);
        heap.createHeap();

        heap.offer(40);
        heap.poll();

        heap.heapSort();
    }
}
